import java.util.Arrays;

public class Solution {
    public static boolean hasPathCore(char[] matrix, int rows, int cols, char[] str,int length, int[] visited, int i, int j){
        if(length==str.length)
            return true;
        //上下左右是否满足条件
        if(i<0 || i>=rows || j<0 || j>=cols || length>str.length)
            return false;

        if(visited[i*cols+j]==0 && matrix[i*cols+j]==str[length]){
            visited[i*cols+j] = 1;
            return hasPathCore(matrix,rows,cols,str,length+1,visited,i-1,j)
                    ||hasPathCore(matrix,rows,cols,str,length+1,visited,i+1,j)
                    ||hasPathCore(matrix,rows,cols,str,length+1,visited,i,j-1)
                    ||hasPathCore(matrix,rows,cols,str,length+1,visited,i,j+1);
        }
        return false;
    }
    public static boolean hasPath(char[] matrix, int rows, int cols, char[] str)
    {
        if(rows*cols!=matrix.length || str.length>matrix.length)
            return false;
        int[] visited = new int[rows*cols];//default 0
        //递归的话就不用自己写栈了，开心//Stack<Character> s = new Stack<>();
        int n=0;
        for(int i=0;i<rows;i++){
            for(int j=0;j<cols;j++){
                Arrays.fill(visited,0);
                //学人家回溯用的递归，好写代码
                if(hasPathCore(matrix,rows,cols,str,0,visited,i,j)){
                    return true;
                }

//                if(m[i][j]==str[n]){
//                    s.add(m[i][j]);
                    //循环遍历有没有与str[n]相等的，如果有，压栈（标志变为1）
                        //判断上下左右（不能越界）有没有与n++， str[n]相同
                            //如果有，继续压栈（标志位改变为1）
                            //如果没有，判断栈是否为空
                                //如果不为空出栈，记录位置。标志先不变，看栈顶有没有其他的与str[n]相同的。
                                    // 如果有，压栈（标志位改变为1），前面出栈的标志变0。
                                    // 如果没有，前面出栈的标志变0，返回上上层。再出栈
                                //如果空，继续往前走。continue，n=0
                                    //如果找到
                                    //如果没有找到返回false
            }
        }


        return false;
    }
    public static void main(String args[]){
//        char[] matrix = {'a','b','c','e','s','f','c','s','a','d','e','e'};
//        char[] str = {'b','c','c','e','d'};
//        char[] str = {'a','b','c','b'};
        char[] matrix = {'a'};
        int rows = 1;
        int cols = 1;
        char[] str = {'a'};
        boolean b = hasPath(matrix,rows,cols,str);
        System.out.println(b);
    }



}

